#include "../../head/myhead.h"

void visit(BTNode *t)
{
    if (t != NULL)
    {
        cout << t->data << " ";
    }
}

void visitThreadBT(TBTNode *t)
{
    if (t != NULL)
    {
        cout << t->data << " ";
    }
}

//见图0.jpg
void createBT(BTNode *t)
{
    t->data = 'A';
    BTNode *t0 = (BTNode *)malloc(sizeof(BTNode));
    t0->data = 'B';
    t->lChild = t0;

    BTNode *t1 = (BTNode *)malloc(sizeof(BTNode));
    t1->data = 'C';
    t->rChild = t1;

    BTNode *t2 = (BTNode *)malloc(sizeof(BTNode));
    t2->data = 'D';
    t0->lChild = t2;
    t0->rChild = NULL;

    BTNode *t3 = (BTNode *)malloc(sizeof(BTNode));
    t3->data = 'E';
    t1->lChild = t3;

    BTNode *t4 = (BTNode *)malloc(sizeof(BTNode));
    t4->data = 'F';
    t1->rChild = t4;

    // BTNode *t5 = (BTNode *)malloc(sizeof(BTNode));
    // t5->data = 'G';
    // t0->rChild = t5;
    // t5->lChild = NULL;
    // t5->rChild = NULL;

    t2->lChild = NULL;
    t2->rChild = NULL;
    t3->lChild = NULL;
    t3->rChild = NULL;
    t4->lChild = NULL;
    t4->rChild = NULL;
}

//见图1.jpg
void createTBT(TBTNode *t)
{
    t->data = 'A';
    TBTNode *t0 = (TBTNode *)malloc(sizeof(TBTNode));
    t0->data = 'B';
    t->lChild = t0;

    TBTNode *t1 = (TBTNode *)malloc(sizeof(TBTNode));
    t1->data = 'C';
    t->rChild = t1;

    TBTNode *t2 = (TBTNode *)malloc(sizeof(TBTNode));
    t2->data = 'D';
    t0->lChild = t2;
    t0->rChild = NULL;

    TBTNode *t3 = (TBTNode *)malloc(sizeof(TBTNode));
    t3->data = 'E';
    t1->lChild = t3;

    TBTNode *t4 = (TBTNode *)malloc(sizeof(TBTNode));
    t4->data = 'F';
    t1->rChild = t4;

    t2->lChild = NULL;
    t2->rChild = NULL;
    t3->lChild = NULL;
    t3->rChild = NULL;
    t4->lChild = NULL;
    t4->rChild = NULL;
}

//先序遍历
//递归方式
void preOrder(BTNode *t)
{
    if (t != NULL)
    {
        visit(t);
        preOrder(t->lChild);
        preOrder(t->rChild);
    }
}
/**
 * 先序遍历非递归方式 双层循环
 * 思路:1.创建一个数组作为栈。
 *      2.循环遍历，访问当前结点，然后将该结点入栈。
 *          2.1一直访问该结点的左子树，直到该结点左子树为空，
 *          2.2然后弹出栈中结点，访问该结点的右子树，重复2，直到栈空且没有子树为止
 */
void preOrderByStack(BTNode *t)
{
    if (t != NULL)
    {
        BTNode *stack[MAXSIZE];
        int top = -1;
        while (t != NULL || top > -1) //树不为空且栈不为空
        {
            while (t != NULL) //循环遍历左子树,同时将结点入栈
            {
                visit(t);
                stack[++top] = t;
                t = t->lChild;
            }
            t = stack[top--];
            t = t->rChild;
        }
    }
}

//中序遍历 递归
void inOrder(BTNode *t)
{
    if (t != NULL)
    {
        inOrder(t->lChild);
        visit(t);
        inOrder(t->rChild);
    }
}
//中序遍历 非递归方式
/**
 * 思路：1.创建一个数组作为栈。
 *      2.循环遍历，将该结点入栈。
 *          2.1一直访问该结点的左子树，直到该结点左子树为空，
 *          2.2然后弹出栈中结点，访问当前结点，访问该结点的右子树，重复2，直到栈空且没有子树为止
 */
void inOrderByStack(BTNode *t)
{
    BTNode *stack[MAXSIZE];
    int top = 0;
    BTNode *p = t;
    while (p != NULL || top > 0)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->lChild;
        }
        p = stack[top--];
        visit(p);
        p = p->rChild;
    }
}

//后序遍历
void postOrder(BTNode *t)
{
    if (t != NULL)
    {
        postOrder(t->lChild);
        postOrder(t->rChild);
        visit(t);
    }
}

//层序遍历
/**
 * 思路：创建一个数组，和两个指针，front，rear，作为一个队列，
 *      将结点入队，然后队头结点出队，将该结点的左孩子和右孩子入队,如此循环直到队列为空
 */
void levelOrder(BTNode *t)
{
    if (t != NULL)
    {
        BTNode *queue[MAXSIZE];
        int front = 0, rear = 0;
        rear = (rear + 1) % MAXSIZE;
        queue[rear] = t;
        while (front != rear)
        {
            front = (front + 1) % MAXSIZE;
            t = queue[front];
            visit(t);
            if (t->lChild != NULL)
            {
                rear = (rear + 1) % MAXSIZE;
                queue[rear] = t->lChild;
            }
            if (t->rChild != NULL)
            {
                rear = (rear + 1) % MAXSIZE;
                queue[rear] = t->rChild;
            }
        }
    }
}

/**
 * 线索二叉树：
 * 思考：二叉树中序遍历（D,B,A,E,C,F）必须从根结点开始，
 * 假设已知结点B，则普通二叉树无法完成遍历，但是使用线索二叉树可以。
 * （详情见1.jpg）线索二叉树指向左子树（右子树）的指针指向前驱结点（后继结点）。例如D指向左子树的指针
 * 指向NULL，只想右子树的指针指向B，例如B结点指向左子树的指针指向D结点，只想右子树的指针指向A结点。
 */
//线索化二叉树 思路：仿照从根节点出发，进行一次中序遍历
void inThread(TBTNode *t, TBTNode *&pre)
{
    if (t != NULL)
    {
        inThread(t->lChild, pre); //递归访问左子树（理同中序遍历）
        if (t->lChild == NULL)    //处理左子树
        {
            t->lChild = pre;
            t->ltag = 1; // tag为1表示该结点指向孩子的指针指向线索，也表示该结点被线索化
        }
        if (pre != NULL && pre->rChild == NULL) //处理右子树
        {
            pre->rChild = t; //建立前驱结点指向的后继线
            pre->rtag = 1;
        }
        pre = t;                  //标记当前结点为刚刚访问过的结点
        inThread(t->rChild, pre); //递归访问右子树（理同中序遍历）
    }
}
void createInThreadTree(TBTNode *t)
{
    if (t != NULL)
    {
        TBTNode *pre = NULL;
        inThread(t, pre);
        pre->rChild = NULL; //处理最后一个结点
        pre->rtag = 1;
    }
}

//线索二叉树的中序遍历
//求中序序列下第一个结点
TBTNode *Firstnode(TBTNode *p)
{
    while (p->ltag != 1) //表示该结点未被线索化，有左子树，则需要找到该左子树的中序遍历的第一个结点
        p = p->lChild;   //最左下结点
    return p;
}
//求结点p在中序序列下的后继
TBTNode *Nextnode(TBTNode *p)
{
    if (p->rtag != 1) //表示该结点未被线索化，有左子树，则需要找到该左子树的中序遍历的第一个结点
        return Firstnode(p->rChild);
    else //否则说明该结点被线索化过，其指向右子树的指针就是指向中序遍历的后继结点
        return p->rChild;
}
//中序线索二叉树的中序遍历算法
void InOrderThreadTree(TBTNode *t)
{
    for (TBTNode *p = Firstnode(t); p != NULL; p = Nextnode(p))
    {
        visitThreadBT(p);
    }
}

/**
 * 哈夫曼树 在含有n个带权叶结点的二叉树中，带权路径长度最小的二叉树
 * 自然语言描述哈夫曼树的构造过程：
 *      1.从结点集合NodeList中取出结点序列中权值最小的两个结点，
 *      2.定义一个新结点temp，temp的权值为这两个最小的和，
 *      3.把temp作为一个新结点加入集合NodeList
 *      4.重复1-3
 */
/**
 * 创建一棵叶子结点数为n的Huffman树
 * 步骤：
 * 1.从结点集合NodeList中取出结点序列中权值最小的两个结点，
 * 2.定义一个新结点temp，temp的权值为这两个最小的和，
 * 3.把temp作为一个新结点加入集合NodeList
 * 4.重复1-3
 */
// void Create_Huffman(unsigned n, HTNode HT[], unsigned m)
// {
//     unsigned int w;
//     int k, j;
//     for (k = 1; k < m; k++)
//     { // 输入时，所有叶子结点都有权值
//         if (k <= n)
//         {
//             printf("\n Please Input Weight : w=?");
//             scanf("%d", &w);
//             HT[k].weight = w;
//         }
//         else
//             HT[k].weight = 0;                           // 非叶子结点没有权值
//         HT[k].parent = HT[k].lChild = HT[k].rChild = 0; // 初始化向量HT
//     }
//     for (k = n + 1; k < m; k++)
//     {
//         unsigned w1 = 32767, w2 = w1; // w1 , w2分别保存权值最小的两个权值
//         int p1 = 0, p2 = 0;           // p1 , p2保存两个最小权值的下标
//         for (j = 1; j <= k - 1; j++)
//         {
//             if (HT[k].parent == 0)
//             { // 尚未合并
//                 if (HT[j].weight < w1)
//                 {
//                     w2 = w1;
//                     p2 = p1;
//                     w1 = HT[j].weight;
//                     p1 = j;
//                 }
//                 else if (HT[j].weight < w2)
//                 {
//                     w2 = HT[j].weight;
//                     p2 = j;
//                 }
//             } /* 找到权值最小的两个值及其下标 */
//         }
//         HT[k].lChild = p1;
//         HT[k].rChild = p2;
//         HT[k].weight = w1 + w2;
//         HT[p1].parent = k;
//         HT[p2].parent = k;
//     }
// }

/**
 * 哈夫曼编码
 */
// m应为n+1,编码的最大长度n加1
// void Huff_coding(unsigned n, HTNode HT[], unsigned m)
// {
//     int k, sp, fp;
//     char *cd, *HC[m];
//     cd = (char *)malloc(m * sizeof(char)); // 动态分配求编码的工作空间
//     cd[n] = '\0';                          // 编码的结束标志
//     for (k = 1; k < n + 1; k++)
//     { // 逐个求字符的编码
//         sp = n;
//         int p = k;
//         fp = HT[k].parent;
//         for (; fp != 0; p = fp, fp = HT[p].parent)
//             ; // 从叶子结点到根逆向求编码
//         if (HT[fp].lChild == p)
//             cd[--sp] = '0';
//         else
//             cd[--sp] = '1';
//         HC[k] = (char *)malloc((n - sp) * sizeof(char)); // 为第k个字符分配保存编码的空间
//         strcpy(HC[k], &cd[sp]);
//     }
//     free(cd);
// }

/**
 * 设计一个算法，判别一颗以二叉链表形式存储的二叉树是否为完全二叉树
 * 思路：使用层序遍历的方法将所有结点入队。当遇到第一个空结点后，如果后面还有结点则不是完全二叉树，否则是完全二叉树
 * 步骤：1.层序遍历
 *      2.若访问到一个null结点，则循环遍历队列，查看队列中是否存在不为空的元素
 */
bool isCompleteTree(BTNode *t)
{
    if (t != NULL)
    {
        bool tag = false;
        BTNode *queue[MAXSIZE];     //用数组模拟一个队列
        int front = 0, rear = 0;
        queue[rear] = t;
        rear = (rear + 1) % MAXSIZE;
        
        while (front != rear)
        { //队列不为空
            BTNode *p = queue[front];
            front = (front + 1) % MAXSIZE;
            if (p != NULL)
            {//当前结点非空，则将左右子树入队
                queue[rear] = p->lChild;
                rear = (rear + 1) % MAXSIZE;
                queue[rear] = p->rChild;
                rear = (rear + 1) % MAXSIZE;
            }else{//结点为空，则检查其后是否有非空结点
                while (front != rear)
                {
                    p = queue[front];
                    front = (front + 1) % MAXSIZE;
                    if (p != NULL)//后面有非空结点，不是完全二叉树
                        return false;
                }
            }
        }
    }
    return true;
}

/**
 * 设给定权值集合w={3,5,7,9,11,12} ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。
 * ans：w = 3*4 + 5*4 + 7*3 + 12*2 + 9*2 + 11*2 = 117
 */

/**
 * 假设二叉树采用二叉链存储结构，设计一个算法，计算一棵给定二叉树的所有叶子结点数。
 * 思路：遍历二叉树，遇到不为空且左右孩子结点为空的结点++
 */
void countLeafNode(BTNode *t, int &n)
{
    if (t != NULL)
    {
        if (t->lChild == NULL && t->rChild == NULL)
        {
            n++;
        }
        countLeafNode(t->lChild, n);
        countLeafNode(t->rChild, n);
    }
}

/**
 * 已知一棵树按顺序存储结构进行存储，设计一个算法，求编号分别为 i 和 j 的两个结点的最近公共祖先结点的值
 */
char valueOfLatelyParent(char data[], int i, int j)
{
    if (i >= 0 && j >= 0)
    {
        i < j ? i /= 2 : j /= 2;
        while (i != j)
        {
            i > j ? i /= 2 : j /= 2;
        }
        return i == j ? data[i] : '\0';
    }
    return '\0';
}

/**
 * 给定一个二叉树T和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
 * 1）.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
 * 2）.叶子节点是指没有子节点的节点
 * 3）.路径只能从父节点到子节点，不能从子节点到父节点
 * 4）.总节点数目为n
 * 思路：遍历二叉树同时将sum与当前值相减，当遍历到叶子结点是判断sum是否为0
 */
int checkPathSum(BTNode *t, int sum)
{
    if (t == NULL)
        return 0; //空结点找不到路径
    // 叶子结点且路径和为sum
    if (t->lChild == NULL && t->rChild == NULL && sum - t->data == 0)
        return 1;
    if (t->lChild != NULL) //递归左子树
        return checkPathSum(t->lChild, sum - t->data);
    if (t->rChild != NULL) //递归右子树
        return checkPathSum(t->rChild, sum - t->data);
}

/**
 * 二叉树的深度
 * 思路：将求该树的最大深度转化为求该结点的左子树和右子树的最大深度，然后+1
 */
int maxDepth(struct BTNode *root)
{
    if (root == NULL)
        return 0;
    return fmax(maxDepth(root->lChild), maxDepth(root->rChild)) + 1;
}

/**
 * 给定一个二叉树，找出其最小深度 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 */
int minDepth(BTNode *root)
{
    if (root == NULL)
        return 0;

    if (root->lChild == NULL && root->rChild == NULL)
        return 1;

    int min_depth = INTMAX;
    if (root->lChild != NULL)
        min_depth = fmin(minDepth(root->lChild), min_depth);

    if (root->rChild != NULL)
        min_depth = fmin(minDepth(root->rChild), min_depth);

    return min_depth + 1;
}

/**
 * 编程求以孩子兄弟链表为存储结构，请设计递归算法求解深度。
 */
typedef struct CSNode
{
    int data;
    struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟指针
} CSNode, *CSTree;
int Height(CSTree T)
{
    if (T == NULL)
        return 0;
    int lheight = Height(T->firstchild);  //第一子女的高度
    int rheight = Height(T->nextsibling); //兄第高度
    // 取第一子女的高度+1和兄弟子树高度的较大者
    if (lheight + 1 > rheight)
        return lheight + 1;
    else
        return rheight;
}

/**
 * 已知一棵树的先序遍历序列和中序遍历序列分别存在于两个一维数组中pre[],in[]，试编写算法建立该二叉树的二叉链表。
 * 思路：先序遍历第一个元素 a 为树的根结点的值。遍历中序遍历列表找到 a ，以此将in[]分为两段。
 * 左边的序列构成左子树，右边构成右子树直到所有子数列只剩下一个元素是构造结束
 */
BTNode *createBTByPreAndIn(char pre[], char in[], int L1, int R1, int L2, int R2)
{
    BTNode *s;
    int i;
    if (L1 > R1)
        return NULL; //如果序列中没有元素，则树为空，返回 NULL

    s = (BTNode *)malloc(sizeof(BTNode)); //申请一个结点空间
    s->lChild = s->rChild = NULL;
    for (i = L2; i <= R2; ++i) //查找等于当前子树根的结点在in[]中的位置
        if (in[i] == pre[L1])
            break;
    s->data = in[i]; //将当前子树根结点值赋给新申请的结点
    /*通过在in[1中找到的分界点i，确定在pre[]和in[]中当前子树的左子树的范围，并参照之前的方法(递归处理)建立左子树，将左子树根连接在s的左指针域上*/
    s->lChild = createBTByPreAndIn(pre, in, L1 + 1, L1 + i - L2, L2, i - 1);
    /*通过在in[]中找到的分界点i,确定在 pre[]和in[]中当前子树的右子树的范围，并参照之前的方法(递归处理)建立右子树，将右子树根速连接在s的右指针域上*/
    s->rChild = createBTByPreAndIn(pre, in, L1 + i - L2 + 1, R1, i + 1, R2);
    return s; //当前子树处理完毕，返回根结点 s
}

BTNode* CreateTree(int post[], int l1, int r1, int in[], int l2, int r2)
{
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = post[r1];
    int i;
    
    for (i = l2; i <= r2; i++)
    { //在中序序列中查找根节点并将其分成左右子树if(in[i]==post[r1]) break;
    }
    int llen = i - l2; //左子树长度
    int rlen = r2-i;//右子树长度
    //递归建立左子树

    if (llen == 0)
    {
        root->lChild = NULL;
    }
    else
    {
        root->lChild = CreateTree(post, l1, l1 + llen - 1, in, l2, l2 + llen - 1);
    }
    //递归建立右子树
    if (rlen == 0)
    {
        root->lChild = NULL;
    }
    else
    {
        root->lChild = CreateTree(post, l1 + llen, r1 - 1, in, r2 - rlen + 1, r2);
    }
    return root; //返回根节点
}

int main()
{
    BTNode *t = (BTNode *)malloc(sizeof(BTNode));
    createBT(t);
    int a = minDepth(t);
    cout << a << endl;
    // preOrderByStack(t);
    // bool a = isCompleteTree(t);

    // int n = 0;
    // countLeafNode(t,n);
    // cout << n;

    // char data[] = {'A', 'B', 'C', 'D', 'E', 'F'};
    // char temp = valueOfLatelyParent(data, 4, 5);
    // cout << temp;

    // levelOrder(t);

    //线索二叉树
    // TBTNode *tt = (TBTNode *)malloc(sizeof(TBTNode));
    // createTBT(tt);
    // createInThreadTree(tt);
    // InOrderThreadTree(tt);
    // TBTNode *temp = Firstnode(tt);
    // cout << endl
    //      << temp->data;
    // temp = Nextnode(temp);
    // cout << endl
    //      << temp->data;

    return 0;
}